package com.fosss.sort;


import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
//        int[] arr={2,6,8,3,-1,1};
//        System.out.println("排序前数组->"+ Arrays.toString(arr));
//        insertionSort(arr);
//        System.out.println("排序后数组->"+Arrays.toString(arr));

        //测试时间复杂度
        //创建一个80000条数据的数组
        int[] arr=new int[80000];
        for(int i = 0; i <80000;i++){
            arr[i]=(int)(Math.random()*80000);
        }
        long startTime = System.currentTimeMillis();
        insertionSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("花费时间"+(endTime-startTime)+"毫秒");//460
    }
    public static void insertionSort(int[] arr){
        for(int i = 0; i < arr.length-1; i++){//需要进行arr.length-1次排序
            int insertValue=arr[i+1];//需要插入得元素为arr[i+1],这里默认将第一个元素看作有序
            int insertIndex=i;//为要插入元素得前一个元素
            while (insertIndex>=0&&insertValue<arr[insertIndex]){
                arr[insertIndex+1]=arr[insertIndex];//将较大的元素后移
                insertIndex--;
            }
            //退出循环说明已经找到插入的位置，且进行插入
            //退出循环说明insertIndex<0,所以需要＋1来恢复为要插入的位置

            arr[insertIndex+1]=insertValue;
        }
    }
}
